package 剑指专题.搜索算法;


/*
 * Author：江松
 * Date：2023/3/29 13:08
 *
 数字序列中的某一位数字：
 1，暴力枚举，超时
 2，位数减法：
 n-9(0-9的1位数)-180(2位数)-2700...

 n=2700 ,n=n-9-180=2511
 对应数字=100+(2511-1)/3
 对应位数=(2511-1)%2——因为是从0开始的
 */

public class Main4 {


    public int findNthDigit (int n) {
        //前几位数的个数，当前几位数的开始值，注意数据范围
        long sum=9,st=1;
        int bit=1;
        while(n>sum){
            n-=sum;
            bit++;
            st*=10;
            sum=9*bit*st;
        }
        //得出第n位所在的数字,当前n是剩下部分位数
        String num=""+(st+(n-1)/bit);//n从0开始
        //得出在这位数上的第几个位置
        int id=(n-1)%bit;
        return num.charAt(id)-'0';
    }
    /*
    //暴力超时
    public int findNthDigit (int n) {
        int i=1,j=0;
        int val=0;
        for(;i<=n;++i){
            int p=1;
            while(true){
                if(p>i/10)break;
                p*=10;
            }
            int t=i;
            while(t!=0&&p!=0){
               val=t/p;
               j++;
               if(j==n)return val;
               t=t%p;
               p/=10;
            }
        }
        return val;
    }
    */

}
